This is the first application filed for the present invention.
Not applicable.
The present invention relates to multicast services, and in particular to a method and apparatus for controlling fanout at an egress node of a dynamic multicast tree in a differentiated services (DS) network.
The recent evolution of communication networks (e.g. the Internet) has increased demand for delivery of dynamic interactive or selective-use differentiated services.
Multicast services include, for example, news or entertainment content, video conferencing for long distance education, or video conferencing for personal or business differentiated services. In this context, a source may be a server at the network edge serving as a source of the content; or an edge node serving as a gateway between affiliated sub-networks, through which the content (which originates elsewhere) is supplied to the sub-network. Similarly, a sink node may be an end-user""communication device (e.g. a personal computer (PC) connected to the network via a modem); or an edge node which serves as a gateway between affiliated sub-networks, and through which the content (having been transported across the sub-network from the source) is supplied to an adjacent sub-network.
In order to enable multicast transport of content, a network provider (NP) must provision the network with both physical and service resources having sufficient band-width capacity. Physical resources are provisioned by installation of the physical plant used to construct the network fabric. Since changes in the physical resources necessarily involves the installation of new hardware, such changes are expensive, and consequently infrequent. Network providers typically utilize various known methods for predicting future bandwidth capacity requirements, and attempt to deploy physical plant having sufficient bandwidth capacity to satisfy anticipated growth in demand for forecast service offerings. However, at least during any specific multicast session, the available physical resources are static, and these may be allocated (typically by allocation of bandwidth and buffers) to multiple differentiated services sessions (or data transport paths) up to a practical limit of the band-width capacity of the physical resource.
The allocation of resources for any communication session is normally conducted during setup of a data transport connection across the network. Various methods are known for service resource allocation, such as, for example, Resource Reservation Protocol (RSVP) and Constrained Routing-Label Distributed Protocol (CR-LDP). In each case, an end-to-end path across the network between source and receiver nodes is first negotiated, and then transport resources along the path are allocated in accordance with a service level specification (SLS) of the communication session. In a situation where the allocation of resources to satisfy the SLS exhausts (or exceeds) the practical capacity of any element (e.g. a node or link) in the path (given pre-existing resource allocations for other differentiated services sessions already utilizing that element), then the path must be abandoned and a new path setup over less congested network elements.
Prior service resource allocation methods are well suited to unicast, and point-to-point (i.e. 1-to-1) connections across the network. In such cases, it is a simple matter to set up a path and allocate resources during setup of the connection. These methods can also be used effectively for multicast groups in which ingress and egress nodes are predetermined and static (i.e. 1-to-Many, in which all egress nodes are predetermined and static) because resource requirements can be accurately predicted prior to setting up the multicast tree. However, in cases where a multicast group is dynamic (i.e. in which any node of the network may serve as an egress node, and/or new egress nodes may join or leave the group during a multicast session), service resources of the network must be provisioned to provide for xe2x80x9c1-to-Anyxe2x80x9d distribution, and it is very difficult to predict provisioning requirements a priori.
In order to overcome this problem Applicant invented a method and system for provisioning network resources for dynamic multicast groups which is described in a Patent Application entitled METHOD AND SYSTEM FOR PROVISIONING NETWORK RESOURCES FOR DYNAMIC MULTICAST GROUPS, issued as U.S. Pat. No. 6,556,544 on Apr. 29, 2003, and is incorporated herein by reference.
Although Applicant""copending patent application addresses the problem of dynamically provisioning a differentiated services network for a dynamic multicast tree, there exists a further multicast provisioning problem that has to date remained unaddressed. That problem is the control of the number of egress points at an ingress node of a dynamic multicast tree. Such control is commonly referred to as the control of xe2x80x9cfanoutxe2x80x9d at the ingress node.
Since an ingress node in a multicast tree has a predetermined bandwidth capacity allocated to any given multicast session, egress points cannot be grafted to the ingress node without regulation. Otherwise, service levels will suffer and the multicast session is likely to intrude on the resources of other services. Egress point grafting to an ingress node of a dynamic multicast tree is not easily controlled, however. The problem is complicated by the dynamic nature of the multicast tree and the unpredictability of how many branches will be required and where the branches are likely to grow.
Consequently, there exists a need for a method and apparatus to permit the control of fanout at an ingress node of a multicast tree. The control is required to enable network service providers to ensure a committed service level in a differentiated services network, while permitting the multicast tree to dynamically respond to access demand within a framework of a service level agreement (SLA) between the service provider and one or more customers that contract for the multicast service.
It is an object of the invention to provide a method and apparatus for controlling fanout at an ingress node of a dynamic multicast tree in a differentiated services network.
A first aspect of the invention therefore provides a method of controlling fanout at an ingress node of a dynamic multicast tree for a multicast session in a differentiated services network. The method is commenced when a graft request message is received from an egress node that has not been joined to the multicast tree. On receipt of the graft request message, the provider egress router sends a graft-request message to the ingress node. A determination is then made as to whether a number of egress points specified by a service level specification (SLS) associated with the multicast session permits the egress node to be grafted. If the graft is permitted, a graft permission response message is sent to the egress node. A graft is allowed if the current number of egress points at the ingress is less than a maximum number stipulated by the SLS.
If the egress mode is not permitted to be grafted, a graft-redirect message is preferably sent from the egress node to a downstream requesting node to permit the downstream requesting node to attempt to graft to an existing branch of the multicast tree instead The graft-redirect message contains addresses of at least one grafted egress node that is already a part of the multicast tree, each grafted egress node providing an alternate site at which the downstream requesting node can attempt to graft to the multicast tree. The downstream requesting node forwards a graft request message to each of the grafted egress nodes in an order in which the addresses are presented in the graft-redirect message, and the downstream requesting node grafts to a first of the grafted egress nodes that accepts the graft. The downstream requesting node sends only one graft request message at a time and waits for a response from the grafted egress node to which the graft request message was sent before sending a next message. If each of the grafted egress nodes refuse to permit the downstream requesting node to graft, the graft attempt is aborted.
In accordance with a further aspect of the invention, a Service Level Specification (SLS) associated with the multicast session may include two or more limits for the number of egress points that may be grafted to an ingress node in a multicast tree. Preferably, a service level is associated with each limit so that service is demoted each time the number of egress points exceeds a limit. Preferably, the SLS specifies a first service level when a number of grafted egress nodes is less than or equal to the first limit, and specifies a second service level if the number of grafted egress nodes is greater than or equal to the second limit, etc. The provider ingress node marks packets associated with the multicast session with the service level corresponding to the current limit.
Messages related to the control of fanout at the ingress node of the multicast tree are preferably diverted to a resource management entity resident in the provider ingress node. The resource management entity is an appropriately modified version of Resource Reservation Protocol (RSVP) or Constrained Routing-Label Distribution Protocol (CR-LDP).
The invention also provides an apparatus for controlling fanout at an ingress node of a dynamic multicast tree for a multicast session in a differentiated services network. The apparatus comprises a resource management entity resident in an ingress node of the dynamic multicast tree. The resource management entity is adapted to store at least one variable, the variable defining a maximum number of egress points that may be grafted to the ingress node. It is also adapted to accept graft request messages from egress nodes requesting to be grafted to the multicast tree. It determines whether a graft requested is to be permitted, given a value variable and a number of pre-existing egress points at the ingress node. The resource management entity is also provided in each provider egress node, and in the provider egress nodes it is adapted to formulate a graft-redirect message that is sent to a downstream requesting node if the egress node cannot be grafted to the ingress node. The graft-redirect message formulated by the resource management entity of the provider egress node contains addresses of at least one egress node that is already grafted to the multicast tree. The address preferably points to an egress node that is proximate the downstream node requesting to be grafted.
The differentiated services network preferably includes a relational database which stores a map of all provider egress nodes involved in a multicast tree. The database is used to select addresses for inclusion in the graft-redirect messages.
The invention also provides a system for controlling fanout at an ingress node of a dynamic multicast tree for a multicast session in a differentiated services network. The system includes a plurality of edge nodes in the differentiated services network, one of the edge nodes being the ingress node. Each of the edge nodes include a respective resource management entity adapted to formulate, send and receive signaling messages related to the management of resources required for the multicast tree. The resource management entities of the edge nodes are also adapted to store at least one variable respecting a maximum number of egress points that may be grafted to the ingress node for the multicast tree. The ingress node is further adapted to receive a graft request message from another edge node in the differentiated services network requesting that the other edge node be permitted to graft to the ingress node of the multicast tree. The ingress node is adapted to determine, using the at least one variable respecting a maximum number of egress points, whether the other edge node can be grafted, and to respond to the other edge node with a response message to inform the other edge node whether it can be grafted to the ingress node. The resource management entity of the ingress node is also adapted to store a service level indicator associated with each of the limits, the service level indicators being used to mark data packets associated with the multicast session. When an edge node in the differentiated services network receives a permission to graft to the multicast tree, the resource management entity of the edge node is adapted to provision service resources for the branch of the multicast tree hop-by-hop as a path for the branch is set up by the resource management entity of the edge node.
The invention also provides a resource management entity for an edge node in a differentiated services network adapted to support dynamic multicast groups. The resource management entity comprises means for storing at least one variable for defining a maximum number of egress points that may be grafted to the edge router when the edge router serves as an ingress node of a multicast tree for a dynamic multicast session. It further comprises means for receiving a graft request message from another node in the differentiated services network, the graft request message requesting permission to graft as a new egress point to the ingress node. It further comprises means for determining whether the graft can be accepted using the at least one variable for defining a maximum number of egress points, and means for informing the other node respecting whether the graft can be accepted.
The invention therefore provides a method and apparatus for automatically controlling fanout at an ingress node in a dynamic multicast tree which enables true dynamic control to permit service to be provided within the bounds of a service level agreement governing the multicast session.